package org.geekbang.time.mathbasicthought.lesson4_induction;

public class Wheat {

    public static void main(String[] args) {
        Result result = new Result();
        System.out.println(prove(63, result));
    }

    /**
     * @param k      放到第几格
     * @param result 保存当前格子的麦粒数和总麦粒数
     * @return 放到第几格时是否成立
     */
    public static boolean prove(int k, Result result) {
        if (k <= 0 || k > 63)
            return false;

        // 证明基本情况成立
        if (k == 1) {
            if (Math.pow(2, k - 1) == 1) {
                result.numOfCurGrid = 1;
                result.numOfTotal += result.numOfCurGrid;
                return true;
            }
        }
        // 再假设n=k-1成立，证明n=k也成立
        else {
            boolean proveOfPreviousOne = prove(k - 1, result);
            result.numOfCurGrid *= 2;
            result.numOfTotal += result.numOfCurGrid;

            boolean proveOfCurOne = false;
            if (result.numOfTotal == (Math.pow(2, k) - 1))
                proveOfCurOne = true;

            if (proveOfPreviousOne && proveOfCurOne)
                return true;
        }
        return false;
    }

    static class Result {
        private double numOfCurGrid = 0;
        private double numOfTotal = 0;
    }
}
